package problems;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

public class Euler079 extends AbstractEuler {

	private String[] keylog = {
		"319",
		"680",
		"180",
		"690",
		"129",
		"620",
		"762",
		"689",
		"762",
		"318",
		"368",
		"710",
		"720",
		"710",
		"629",
		"168",
		"160",
		"689",
		"716",
		"731",
		"736",
		"729",
		"316",
		"729",
		"729",
		"710",
		"769",
		"290",
		"719",
		"680",
		"318",
		"389",
		"162",
		"289",
		"162",
		"718",
		"729",
		"319",
		"790",
		"680",
		"890",
		"362",
		"319",
		"760",
		"316",
		"729",
		"380",
		"319",
		"728",
		"716"
	};
	
	@Override
	public Number calculate() {
		StringBuffer answer = new StringBuffer();
		
		//the key follows every Character in the Set of the value on at least one occasion
		Map<Character,Set<Character>> ordering = new ConcurrentHashMap<Character,Set<Character>>();
		
		//fill the map
		for (String digits : keylog) {
			Character one = Character.valueOf(digits.charAt(0));
			Character two = Character.valueOf(digits.charAt(1));
			Character three = Character.valueOf(digits.charAt(2));
			if (ordering.get(one)	== null)	ordering.put(one,	new HashSet<Character>());
			if (ordering.get(two)	== null)	ordering.put(two,	new HashSet<Character>());
			if (ordering.get(three)	== null)	ordering.put(three,	new HashSet<Character>());
			
			ordering.get(two).add(one);
			ordering.get(three).add(one);
			ordering.get(three).add(two);
		}
		
		going_for_bust:
		while (!ordering.isEmpty()) {
			Iterator<Entry<Character, Set<Character>>> candidates = ordering.entrySet().iterator();

			//look for a character that is not behind any other (i.e., it's the first character)
			while (candidates.hasNext()) {
				Entry<Character,Set<Character>> candidate = candidates.next();
				if (candidate.getValue().isEmpty()) {
					//found what must be the next first character in the passcode
					Character theFirst = candidate.getKey().charValue();

					//move it to the answer holder
					answer.append(theFirst);
					ordering.remove(theFirst);
					
					//remove it from further consideration, so in the next iteration we can see
					//which character is now not following any others
					for (Set<Character> value : ordering.values()) {
						value.remove(theFirst);
					}
					
					//keep going until we have moved all characters into the answer in the right order
					continue going_for_bust;
				}
			}
		}
		
		
		return new BigInteger(answer.toString());
	}

	@Override
	protected Number getCorrectAnswer() {
		return new BigInteger("73162890");
	}

}
